引言
基于循环的算法的时间复杂度通常比较容易分析。例如用于求最短路径的Bellman-Ford算法,由于两层循环,它的时间复杂度为Θ(NM)。
相比之下,递归算法的时间复杂度分析起来会更难一些。我们常用的许多算法都有递归调用,其中分治法是递归算法的一大类。
多数递归算法都有这几点特征:当处理一个问题时,先将它分解成几个规模更小的子问题,分别递归求解子问题,最后处理子问题的结果得到答案。当问题足够小时,就可以不用分解直接得到答案,即递归存在边界。
下面举出几个具体例子,分析这类算法的时间复杂度。
① 归并排序
对数组A的某个区间[l,r]排序。
我们可以选取mid=⌊2l+r⌋,递归对区间[l,mid]和[mid+1,r]排序,然后对两个有序的区间进行归并。
递归的一个边界是l=r,即区间长度为1时无需排序。
记排序长度为n的区间所需的时间为f(n),因为每次分成两个子问题,子问题的规模缩小一半,归并需要Θ(n)的时间,可以得到以下递归式:
f(n)=Θ(n)+2f(2n),n>1
f(1)=Θ(1)
注意:上面给出的递归式省略了取整符号。正常情况下,归并排序的时间复杂度递归式应该为
f(n)=Θ(n)+f(⌊2n⌋)+f(⌈2n⌉),n>1
,为了计算方便,我们只考虑n为2的整数幂的情况,也就省略了取整符号。这对最后得出的时间复杂度渐进表示没有影响。下面的例子也同样。
② Strassen算法
Strassen算法是用来求矩阵乘法的分治算法。对于两个n×n的矩阵相乘,它将每个矩阵分解为四个2n×2n的小矩阵,利用这些小矩阵计算出十个2n×2n矩阵的和或差,然后递归七次计算矩阵乘法,最后用子问题得到的矩阵加减运算得到答案。分解子问题和归并都需要Θ(n2)的时间。递归的边界为n=1。
它的时间复杂度递归式是:
f(n)=Θ(n2)+7f(2n),n>1
f(1)=Θ(1)
算法的具体实现这里并不进行讲解。
③ 寻找第k大
在一个数组A的某个区间[l,r]上,寻找第k大的值。
我们可以随便选取一个在[l,r]里出现过的值mid,并用Θ(n)的时间把所有小于mid的元素交换到mid左边,所有大于mid的元素交换到右边(就像快速排序那样)。此时可以得到mid的排名p,如果k<p则递归寻找左区间的第k大,k>p则递归寻找右区间的第k−p大,否则直接返回mid。递归的一个边界是l=r。
由于平均情况下我们可以把子问题缩小一半(这其实是不严谨的,这里举这个例子仅仅为了引出递归式,后面我们会用另一种方法推导它的平均复杂度),依然可以得到递归式:
f(n)=Θ(n)+f(2n),n>1
f(1)=Θ(1)
一般形式的数学推导
对于以上两个递归式,都可以变形为一个更一般的形式:
f(n)=Θ(nt)+kf(mn),n>1
f(1)=Θ(1)
其中参数的取值范围t≥0,m>1,k>0
如何用数学方法得到这个递归式的渐进表示?
首先,我们可以移去对最后结果没有影响的渐进符号(不严谨地说,渐进符号其实就是乘了一个常数)。即
f(n)=nt+kf(mn),n>1
f(1)=1
这样f(n)变成了一个关于n的确定的函数。上文已经说到,因为省略了取整符号,只考虑n为m的整数幂的情况。于是:
f(1)=1
f(m)=k+mt
f(m2)=k2+kmt+m2t
......
f(ma)=ka+ka−1mt+...+km(a−1)t+mat=∑i=0aka−imit
这是一个等比数列的求和,它的公比是kmt。
不过我在这里并不想使用等比数列的求和公式。我要使用的是这个:
1+x+x2+x3+...=1−x1,0<x<1
这个公式表示的是一个公比小于1的正项等比数列无穷项的和。它还告诉我们,这个数列前任意项的和一定小于某个常数(利用上面的结论),因为公比是确定的。
回到刚才的f(ma)上来。因为公比kmt是一个确定的常数,如果它小于1,那么f(ma)一定小于ka乘以某个常数。所以f(ma)=Θ(ka)。
令ma=n,则有f(n)=Θ(klogmn)=Θ(nlogmk),mt<k。
这样我们就可以解决第二个例子Strassen算法的时间复杂度:把t=2,k=7,m=2代入,即有f(n)=Θ(nlog27)。
接下来讨论公比kmt=1的情况。很明显等比数列的所有项都相等,一共有logmn+1项,总和为(logmn+1)nt=Θ(ntlogn)。
这种情况对应第一个例子归并排序,把t=1,k=2,m=2代入,即有f(n)=Θ(nlogn)。
只剩下最后一种情况,kmt>1。
考虑等比数列求和正反求都一样,可以把整个数列反着写,于是形成了一个新的等比数列,它的首项是原数列的末项,公比是原数列的倒数。
再次应用上面的结论,我们得到:
f(n)=Θ(mat)=Θ(nt),mt>k。
这对应了第三个例子:代入t=1,k=1,m=2,得到
f(n)=Θ(n)
综上所述
对于以下形式的递归式
f(n)=Θ(nt)+kf(mn),n>1
f(1)=Θ(1)
t≥0,m>1,k>0
有
f(n)=Θ(nlogmk),mt<k
f(n)=Θ(ntlogn),mt=k
f(n)=Θ(nt),mt>k
随机数据与平均复杂度
很多情况下,子问题的规模并不是确定的。例如上面的例子“寻找第k大”,当处理长度为n的区间时,子问题的规模是1到n−1中的一个数,它取决于数据,包括k的值和每次选择的mid值。
在最坏情况下,子问题的规模一直是n−1,递归式会变为
f(n)=Θ(n)+f(n−1)=Θ(n2)
但是,通常情况下,最坏情况出现的概率极低,我们关心的是其在随机数据下的平均复杂度。
如果数据是随机数据,k也是随机取的,那么子问题的规模就会是[1,n−1]中的一个随机值,且子问题的k也是随机值。
那么,我们会得到下面的递归式:
f(n)=Θ(n)+f(n),n>1
f(1)=Θ(1)
其中f(n)=n−1∑i=1n−1f(i)表示f(1)到f(n−1)的平均值。
数学归纳法
对于这个递归式,依然移去渐进符号:
f(n)=n+f(n),n>1
f(1)=1
容易看出f(n)=2n−1,证明也比较简单,简单粗暴的数学归纳法:
设对于任意n0<n满足f(n0)=2n0−1,则
f(n)=n−1∑i=1n−1f(i)=n−1n(n−1)−(n−1)=n−1
f(n)=n+f(n)=2n−1=Θ(n)
又因f(1)=1,结论得证。
考虑另一个问题,把上面的递归式改为f(n)=n+2f(n)
我们猜想f(n)=Θ(nlogn),尝试用数学归纳法证明:
设对于任意n0<n满足f(n0)≤cn0log(n0)+a,欲证f(n)≤cnlog(n)+a
不太好弄,可以玩一个小技巧,因为∑i=1ni1=Θ(logn),定义d(n)=∑i=1ni1,并用d(n)换原式中的log(n)
设对于任意n0<n满足f(n0)≤cn0d(n0)
经过计算2f(n)≤cnd(n)−2cn
只要c≥2,即有f(n)≤cnd(n)=Θ(nlogn)
又f(1)≤c,结论得证。
其实f(n)=2nd(n)−n
结语
递归算法多种多样,时间复杂度的推导也各不相同。这里举了几种简单的例子,其他的情况还需大家思考。
如有错误,还请各位指正